BOJ_18428_감시피하기

장애물은 꼭 3개가 설치되어야 하기 때문에, 선생님과 학생이 없는 빈 자리 중 3개를 뽑아 완전 탐색으로 모든 경우를 확인한다

임의의 장애물 3개를 뽑았다면 선생님의 좌표에서 학생이 보이는지를 테스트 한다
선생님 좌표는 고정된 상태이기 때문에 입력을 받을 때 저장해두었다

package BJO;  
  
import java.util.ArrayList;  
import java.util.List;  
import java.util.Scanner;  
  
public class BJO_18428_감시피하기 {  
    static int N;  
    static String[][] arr;  
    static int[] dy = {0, 0, -1, 1};  
    static int[] dx = {1, -1, 0, 0};  
    static List<int[]> teacherIdx;  
  
    public static void main(String[] args) {  
        Scanner scan = new Scanner(System.in);  
        teacherIdx = new ArrayList<>();  
        // 입력  
        N = scan.nextInt();  
        arr = new String[N][N];  
        for (int i = 0; i < N; i++) {  
            for (int j = 0; j < N; j++) {  
                arr[i][j] = scan.next();  
  
                // 선생님 좌표를 미리 저장하기  
                if (arr[i][j].equals("T")) {  
                    teacherIdx.add(new int[]{i, j});  
                }  
            }  
        }  
  
        // 장애물 선택하기  
        choose(0, 0, 0);  
        System.out.println("NO");  
    }  
  
    static void choose(int y, int x, int cnt) {  
        if (cnt == 3) {  
            test();  
            return;  
        }  
  
        for (int i = 0; i < N; i++) {  
            for (int j = 0; j < N; j++) {  
                // 이전에 탐색한 좌표를 탐색하지 않기 위한 장치  
                if (i == 0 && j == 0 && !(y == 0 && x == 0)) {  
                    i = y;  
                    j = x;  
                    continue;  
                }  
  
                // 빈 칸에 장애물 놓기  
                if (arr[i][j].equals("X")) {  
                    arr[i][j] = "O";  
                    choose(i, j, cnt + 1);  
                    arr[i][j] = "X";  
                }  
            }  
        }  
    }  
  
    static boolean findStudent(int yy, int xx) {  
        for (int i = 0; i < 4; i++) {  
            int y = yy;  
            int x = xx;  
  
            // 한 방향으로 나아가기  
            while (true) {  
                y += dy[i];  
                x += dx[i];  
  
                if (y < 0 || y >= N || x < 0 || x >= N || arr[y][x].equals("O")) {  
                    break;  
                }  
  
                if (arr[y][x].equals("S")) {  
                    return false;  
                }  
            }  
        }  
  
        return true;  
    }  
  
    static void test() {  
        for (int[] idx : teacherIdx) {  
            if (!findStudent(idx[0], idx[1])) {  
                return;  
            }  
        }  
  
        System.out.println("YES");  
        System.exit(0);  
    }  
}

#완전탐색